package com.leetcode.根据数据结构分类.二叉树;

import com.leetcode.datastructure.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author: ZhouBert
 * @date: 2021/2/26
 * @description: 剑指 Offer 36. 二叉搜索树与双向链表
 * https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
 */
public class B_剑指Offer36_二叉搜索树与双向链表 {

	public static void main(String[] args) {
		B_剑指Offer36_二叉搜索树与双向链表 action = new B_剑指Offer36_二叉搜索树与双向链表();
		test1(action);
//		test2(action);
	}

	public static void test1(B_剑指Offer36_二叉搜索树与双向链表 action) {
		// 3
		TreeNode root = TreeNode.stringToTreeNode("[4,2,5,1,3]");
		TreeNode res = action.treeToDoublyList(root);
		System.out.println("res = " + res);
	}

	public static void test2(B_剑指Offer36_二叉搜索树与双向链表 action) {
		// 3
		TreeNode root = TreeNode.stringToTreeNode("[1]");
		TreeNode res = action.treeToDoublyList(root);
		System.out.println("res = " + res);
	}


	/**
	 * 其实就是对于二叉树的中序遍历
	 * 左- 中 - 右
	 * --
	 * 这是一个非原地算法，但是题目要求是原地算法
	 *
	 * @param root
	 * @return
	 */
	public TreeNode treeToDoublyListNoLocal(TreeNode root) {
		if (root == null) {
			return root;
		}
		Deque<TreeNode> deque = new LinkedList();
		treeToDeque(root, deque);
		//重新编号
		TreeNode headNode = deque.removeFirst();
		TreeNode preNode = headNode;
		TreeNode cur = headNode;
		while (!deque.isEmpty()) {
			cur = deque.removeFirst();
			preNode.right = cur;
			cur.left = preNode;

			preNode = cur;
		}
		headNode.left = cur;
		cur.right = headNode;
		return headNode;
	}

	/**
	 * 将节点放入队列
	 *
	 * @param root
	 * @param deque
	 */
	private void treeToDeque(TreeNode root, Deque<TreeNode> deque) {
		if (root.left != null) {
			treeToDeque(root.left, deque);
		}
		//
		deque.addLast(root);

		if (root.right != null) {
			treeToDeque(root.right, deque);
		}
	}

	TreeNode h, p;

	/**
	 * 由于是通过原地算法，所以不能使用循环来完成，终究还是需要递归
	 *
	 * @param root
	 * @return
	 */
	public TreeNode treeToDoublyList(TreeNode root) {
		if (root == null) {
			return root;
		}

		dfs(root);

		h.left = p;
		p.right = h;
		return h;
	}

	/**
	 * 深度优先遍历
	 * 【这里有个小技巧我木有想到：将 pre 作为全局变量，这样方便使用】
	 *
	 * @param root
	 * @return
	 */
	private void dfs(TreeNode root) {
		if (root.left != null) {
			dfs(root.left);
		}

		if (h == null) {
			h = root;
		} else {
			//不为头结点时不仅需要处理它自身的next指针（root.left = pre）
			//还需要让链表前一结点的next指向当前节点，也就是pre.right = root;
			p.right = root;
		}
		root.left = p;
		p = root;

		if (root.right != null) {
			dfs(root.right);
		}

	}

}
